package com.zhaopin.tree;

import java.util.*;

/**
 * @author yin.peide
 * @date 2021-06-17 16:45
 * <p>
 * 判断一棵树是否是完全二叉树
 */
public class FullTree {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node4.setLeft(node2);
        node4.setRight(node6);
//        node2.setLeft(node1);
        node2.setRight(node3);
        node6.setLeft(node5);
        node6.setRight(node7);

        List list = breadthTraversal(node4);

        System.out.println(list);

        System.out.println(isfullTree(node4) ? "是完全树" : "不是完全树");

    }


    /**
     * 广度遍历
     *
     * @param treeNode
     * @return
     */
    public static List<Integer> breadthTraversal(TreeNode treeNode) {
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if (null == treeNode.getLeft() && null == treeNode.getRight()) {
            return list;
        }

        //先插入队列
        queue.offer(treeNode);

        while (!queue.isEmpty()) {
            TreeNode tree = queue.poll();

            TreeNode treeNodeLeft = tree.getLeft();
            TreeNode treeNodeRight = tree.getRight();

            if (Objects.nonNull(treeNodeLeft)) {
                queue.offer(treeNodeLeft);
            }
            if (Objects.nonNull(treeNodeRight)) {
                queue.offer(treeNodeRight);
            }

            list.add(tree.getValue());
        }
        return list;
    }

    /**
     * 通过广度遍历判断是否是完全树
     *
     * @param treeNode
     * @return
     */
    public static boolean isfullTree(TreeNode treeNode) {
        Queue<TreeNode> queue = new LinkedList<>();

        if (null == treeNode.getLeft() && null == treeNode.getRight()) {
            return true;
        }

        //先插入队列
        queue.offer(treeNode);

        while (!queue.isEmpty()) {
            TreeNode tree = queue.poll();

            TreeNode treeNodeLeft = tree.getLeft();
            TreeNode treeNodeRight = tree.getRight();

            if (Objects.nonNull(treeNodeLeft)) {
                queue.offer(treeNodeLeft);
            }
            if (Objects.nonNull(treeNodeRight)) {
                queue.offer(treeNodeRight);
            }

            //此处是关键
            //某个树的节点只有一个子分支，包含右子分支或者左子分支
            boolean isTreeHaveOnlyOneBranch = (Objects.isNull(treeNodeLeft) && Objects.nonNull(treeNodeRight)) || (Objects.nonNull(treeNodeLeft) && Objects.isNull(treeNodeRight));

            if (isTreeHaveOnlyOneBranch) {
                return false;
            }

        }
        return true;
    }

}
